package oct2013;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class GenerateParentheses {
	public ArrayList<String> generateParenthesis(int n) {
		ArrayList<String> res = new ArrayList<String>();
		Queue<String> q = new LinkedList<String>();
		q.add("");
		while (!q.isEmpty()) {
			String str = q.poll();
			if (str.length() == n << 1) {
				res.add(str);
			} else {
				int cnt = count(str);
				if (cnt > str.length() - cnt && str.length() - cnt < n) {
					q.add(str + ")");
				}
				if (cnt < n) {
					q.add(str + "(");
				}
			}
		}
		return res;
	}

	int count(String s) {
		int cnt = 0;
		for (int i = 0; i < s.length(); ++i) {
			if (s.charAt(i) == '(')
				cnt++;
		}
		return cnt;
	}
}
